Let delta(n) denote the self-circumference of a regular polygon with n sides. It will be shown that delta (n) is monotonically increasing from 6 to 2 pi if n is twice and odd number, and monotonically decreasing from 8 to 2 pi if n is twice an even number. Calculation of delta (n) for the case where n is odd as well as inequalities for self-circumference of some irregular polygons are given. Properties of the mixed area of a plane convex body and its polar dual are used to discuss the...

Topics: DTIC Archive, Ghandehari, Mostafa, NAVAL POSTGRADUATE SCHOOL MONTEREY CA, *POLYGONS, MIXING, CONVEX...

We consider the problem of finding a shortest watchman route from which the exterior of a polygon is visible (external watchman route). We present an O(n to the 4th power loglogn) algorithm to find shortest external watchman routes for simple polygons by transforming the external watchman route problem to a set of internal watchman route problems. Also, we present faster external watchman route algorithms for special cases. These include optimal O(n) algorithms for convex, monotone, star and...

Topics: DTIC Archive, Ntafos, Simeon, NEVADA UNIV LAS VEGAS, *ALGORITHMS, *POLYGONS, *ROUTING,...

The problem of finding minimum guard covers in NP-hard for simple polygons and open for simple orthogonal polygons. Alternative definitions of visibility have been considered for orthogonal polygons. In this paper we try to determine the complexity of finding guard covers in orthogonal polygons by considering periscope visibility. Under periscope visibility two points in an orthogonal polygon are visible if there is an orthogonal path with at most one bend that connects them without...

Topics: DTIC Archive, Gewali, Laxmi, NEVADA UNIV LAS VEGAS, *PERISCOPES, *NONLINEAR PROGRAMMING,...

In this paper, we propose and analyze two algorithms to monitor an environmental boundary with mobile sensors. The objective is to optimally approximate the boundary with a polygon. In the first scenario the mobile sensors know the boundary and the approximating polygon is defined by the sensors' positions. In the second scenario the mobile sensors rely only on sensed local information to position some interpolation points and define an approximating polygon. For both scenarios we design...

Topics: DTIC Archive, Susca, Sara, CALIFORNIA UNIV SANTA BARBARA, *ROBOTICS, *DETECTORS, *MONITORING,...

Consider a scenario where a military intelligence ground-operative encounters an array of radars during a reconnaissance mission in enemy territory, where the shape of the array is important to determine its purpose. However, he does not have requisite gadgets to make any accurate positional assessment about the array. He starts noting down the approximate angular direction of each radar from its previous radar position in the array, with respect to the North (say, by observing the Pole Star in...

Topics: DTIC Archive, Mitra, Debasis, FLORIDA INST OF TECH MELBOURNE, *ANGLES, *DIRECTION FINDING,...

This document defines a geometric figure which is called an anti-cylinder, like the cylinder, it has a bottom circle gamma function and a topcircle gamma function' and all common normals of gamma function and gamma function' have the same length c. Figure 2 exhibits a model made by the author of 1 1/2 feet height. Unlike the two circles of a cylinder the circles gamma function and gamma function' are linked, like two consecutive elements in a chain. If made of anodized aluminum tubing and of...

Topics: DTIC Archive, Schoenberg,I J, WISCONSIN UNIV-MADISON MATHEMATICS RESEARCH CENTER, *CIRCLES,...

The paper surveys techniques for filling in n-sided regions, where n > 4. The two major classes of methods examined are: (1) to fill in the hole with 4 and/or 3 sided patches, and (2) to create a single surface. The multi-patch approaches differ in terms of the degree of the patches and the cross-patch continuity. The single surface approaches are either rational surfaces (which can be expressed in terms of base points) or non-rational, both cases having a number of variants.

Topics: DTIC Archive, Malraison, Pierre, SPATIAL TECHNOLOGY INC BOULDER CO, *APPROXIMATION(MATHEMATICS),...

It is well known that the convex hull of a set of n points in the (Euclidean) plane can be found by an algorithm having worst-case complexity O(n log n). In this note we give a short linear algorithm for finding the convex hull in the case that the (ordered) set of points from the vertices of a simple (i.e., non-self-intersecting) polygon. (Author)

Topics: DTIC Archive, Graham,Rondld L, STANFORD UNIV CA DEPT OF COMPUTER SCIENCE, *Convex sets, *Polygons,...

A facet of a convex polytope C is the intersection of C with a supporting hyperplane. Since the extreme points (extrema) of a facet F of C are just the extreme of C that lie in F, a facet is completely described by the list of its extrema. In the following we may not distinguish among: (a) a polytope; (b) the set of extrema of the polytope; (c) the set of coordinate vectors of the extrema of the polytope; (d) the set of vertices of the graph G corresponding to the rows of Z that are coordinate...

Topics: DTIC Archive, Powers, David L, CLARKSON UNIV POTSDAM NY DEPT OF MATHEMATICS AND COMPUTER SCIENCE,...

We present a new approach to Hermite subdivision schemes. It is based on the observation that a sequence of second order Hermite data define a unique interpolating cubic C(sup 1) spline. The B-Spline form of this interpolating spline leads to a stationary binary subdivision scheme with 4 different subdivision rules for the control points. We construct a generalized 4-point scheme which leads to a new family of C(sup 2) Hermite subdivision schemes.

Topics: DTIC Archive, Schwanecke, U., Juettler, B., JOHANNES KEPLER UNIV LINZ (AUSTRIA), *CUBIC SPLINE...

The subject of the finite Fourier series and some new applications to problems of elementary geometry are applied to a theorem of Jesse Douglas on skew pentagons in space. It is shown here that Douglas' theorem amounts to the graphical harmonic analysis of skew pentagons and that it is also the source of striking outdoor sculptures. (Author)

Topics: DTIC Archive, Schoenberg,I J, WISCONSIN UNIV-MADISON MATHEMATICS RESEARCH CENTER, *FOURIER SERIES,...

The goal of this research project was to investigate new methods of representing and manipulating three-dimensional geometric models using volumetric techniques. Three sub-areas were particular targets for these investigations: 1) explore ways of extending the kinds of models that can be represented volumetrically, 2)create multiresolution models using volume techniques, and 3) perform shape transformation using a volumetric framework.

Topics: DTIC Archive, Turk, Greg, GEORGIA TECH RESEARCH CORP ATLANTA, *COMPUTERIZED SIMULATION, *GEOMETRIC...

A user-friendly divide-and-conquer algorithm is presented for finding all the self intersection points of a parametric curve in the Bernstein-Bezier representation. The underlying idea of the algorithm is to deal with the Bexier polygon instead of the curve description itself. By alternately subdividing the Bezier polygon and estimating the self intersection regions the self intersection points are finally approximated by straight line intersections of the refined Bezier polygons. The algorithm...

Topics: DTIC Archive, Lasser, Dieter, NAVAL POSTGRADUATE SCHOOL MONTEREY CA, *CURVES(GEOMETRY), ALGORITHMS,...

Errors often occur in transferring electronic data, ranging from sensitive government information to everyday bar codes. Encoding information with an error-correcting code can alleviate the problem of corrupt or lost data. In order to not overburden computing systems, an efficient code must be used that will quickly encode and decode data while detecting and correcting a large number of errors. The goal of this project is to construct and develop efficient codes using recent advances in...

Topics: DTIC Archive, NAVAL ACADEMY ANNAPOLIS MD, *CODING, ALGEBRAIC GEOMETRY, EFFICIENCY, ERROR CORRECTION...

Given a graph G, an independent set I(G) is a subset of the vertices of G such that no two vertices in I(G) are adjacent. The independence number alpha(G) is the order of the largest set of independent vertices. In this paper, we study the independence number for the Generalized Petersen graphs, finding both sharp bounds and exact results for subclasses of the Generalized Petersen graphs.

Topics: DTIC Archive, NAVAL POSTGRADUATE SCHOOL MONTEREY CA DEPT OF APPLIED MATHEMATICS, *GRAPHS, APPLIED...

The basis of this project was to complete the 2-way conversion between Stanford PLY and Ballistic Research Laboratory Computer-Aided Design (BRL-CAD) file formats by utilizing the open source C RPly library. The existing converter that converts Stanford PLY files to BRL-CAD s file format was improved by implementing binary PLY file support and increasing overall speed. Binary PLY files are much smaller and quicker to process, and are necessary for large data. Then, a converter was developed...

Topics: DTIC Archive, AMERICAN SOCIETY FOR ENGINEERING EDUCATION WASHINGTON DC, *COMPUTER AIDED DESIGN,...

This report shall focus attention on the specification of the edge process, and show how various geometrical insights suggests how the prior Gibbs distribution should be constructed. The discussion will suggest relative costs for possible configurations somewhat different from those proposed by Geman and Geman (1984). In addition the scheme will provide methods for dealing with rectangular and irregular pixel patterns. The general idea of evolving penalties for continuation configurations based...

Topics: DTIC Archive, Brown, Timothy C, STANFORD UNIV CA DEPT OF STATISTICS, *EDGES, CONSISTENCY, COSTS,...

This paper deals with the subject of the first chapter of the second author's book Mathematical Time Exposures: The equidecomposability of a regular triangle and a square of equal areas. A new solution of the problem is given, which also shows that the solution of the problem as given in the third edition of Hogo Steinhaus 'Mathematical Snapshots', is not correct. (Author)

Topics: DTIC Archive, Crowe,D W, WISCONSIN UNIV-MADISON MATHEMATICS RESEARCH CENTER, *Polygons, *Triangles,...

This document presents an orner n algorithm which computes the convex hull of a two-dimensional non-self-intersecting polygon. The algorithm recovers much of the simplicity of the one presented by Sklansky and subsequently disproved. Unlike several algorithms which have been found since then, the modified algorithm executes a truly uniform (modeless) traversal of all the vertices of the polygon. This makes it possible to extend the algorithm to extract geometric information about the interior...

Topics: DTIC Archive, Peshkin,M A, CARNEGIE-MELLON UNIV PITTSBURGH PA ROBOTICS INST, *ALGORITHMS,...

Spatial queries are a fundamental class of queries on geographic data that consist primarily of points, lines, and polygons. Enhancing response time of spatial queries requires a spatial index. The chaintree is a dynamic spatial index structure being developed at RAND, based on a regular planar straight line graph. The chaintree organizes polygons to efficiently answer spatial queries. An operation basic to most chaintree procedures is polygon intersection. This Note presents a new algorithm...

Topics: DTIC Archive, Shane, Darrell H, RAND CORP SANTA MONICA CA, *ALGORITHMS, *INTERROGATION, *MONOTONE...

Topics: DTIC Archive, Arkin, Esther M, CORNELL UNIV ITHACA NY, *POLYGONS, *SHAPE, *METRIC SYSTEM, COMPUTER...

This paper presents all possible isomerizations involving the 34 combinatorially distinct seven-vertex polyhedra. Such isomerizations are expressed in the form P sub 1 yields P sub 2 yields P sub 3 in which P sub 1 and P sub 3 have the same number of edges and the intermediate polyhedron P sub 2 has fewer edges than P sub 1 or P sub 3. Isomerizations of this type are regarded as degenerate if P sub 1 is combinatorially equivalent to P sub 3 and planar if P sub 2 is a planar polygon. Non-planar...

Topics: DTIC Archive, King,R B, GEORGIA UNIV ATHENS DEPT OF CHEMISTRY, *ISOMERIZATION, *MOLECULAR...

The ability to make computer images more realistic is becoming more important as the hardware for producing such images is becoming less expensive and hence more available. The key to producing realistic images lies in the algorithms that can take full advantage of the hardware to produce them. In this study, we look at a prototype of one ray tracer. Ray tracing, in combination with a global illumination model, currently provides the most realistic images that can be generated on general...

Topics: DTIC Archive, Smith, Paul G, NAVAL POSTGRADUATE SCHOOL MONTEREY CA, *MODELS, *IMAGES, *SHADOWS,...

Scott has recently studied two simple variations on the ordinary histogram, namely the frequency polygon and the average shifted histogram, and found that they are able to compete with for example kernel density estimators in performance while retaining the advantage of being conceptually and computationally simple. The present paper proposes a way of generalizing frequency polygons to d-dimensional space that performs better than Scott's generalization. Expressions for integrated mean squared...

Topics: DTIC Archive, Hjort, Nils L., STANFORD UNIV CA LAB FOR COMPUTATIONAL STATISTICS, *ERROR ANALYSIS,...

This paper presents a new method of grouping edges in order to recognize objects. This grouping method succeeds on images of both two- and three-dimensional objects. So that the recognition system can consider first the collections of edges most likely to lead to the correct recognition of objects, we order groups of edges based on the likelihood that a single object produced them. The grouping module estimates this likelihood using the distance that separates edges and their relative...

Topics: DTIC Archive, Jacobs, David W, MASSACHUSETTS INST OF TECH CAMBRIDGE ARTIFICIAL INTELLIGENCE LAB,...

Surface formulation of method of moments gives the best results in electromagnetic analysis when geometrical modeling is performed with quadrilateral patches. Quadrilateral modeling, however, can be very difficult. Many structures, e.g. different microwave devices, can be easily modeled using polygonal surfaces. This paper presents general method for conversion of polygonal model into quadrilateral model. Proposed method is illustrated on real microwave filter.

Topics: DTIC Archive, Tasic, Miodrag S, BELGRADE UNIV (YUGOSLAVIA) FACULTY OF ELECTRICAL ENGINEERING,...

This paper applies the technique of the h-p version to the boundary element method for boundary value problems on non-smooth, plane domains with piecewise analytic boundary and data. The exponential rate of convergence of the boundary element Galerkin solution is proven when a geometric mesh refinement towards the vertices is used. (KR)

Topics: DTIC Archive, Babuska, I, MARYLAND UNIV COLLEGE PARK INST FOR PHYSICAL SCIENCE AND TECHNOLOGY,...

In this notebook we present a collection of three new results in planar computational geometry. The first problem is to test a given n-vertex simple polygon for monotonicity; this problem can be optimally solved in time theta(n). The second result is an improved algorithm for the rectangle enclosure problem; this algorithm improves over an existing one by using optimal space theta(n). Finally, the third result is the construction, in time 0(nlogn), of the shortest path between two points in the...

Topics: DTIC Archive, Preparata,F P, ILLINOIS UNIV AT URBANA APPLIED COMPUTATION THEORY GROUP,...

The classical error estimates for the h-version of the finite element method are extended for the h-p version. The estimates are expressed as explicit functions of h and p are shown to be optimal. The estimates are given for the case where the solution u (H sub k and the case when u has singularities at the corners of the domain. (Author)

Topics: DTIC Archive, Babuska,Ivo, MARYLAND UNIV BALTIMORE COUNTY BALTIMORE DEPT OF MATHEMATICS, *FINITE...

In this paper, we deal with the monotonicity of curvature problem for Bezier-de Casteljau curves. We focus more particularly on the cubic case. A condition about decreasing curvature at the origin of a cubic curve is given so that it implies decreasing curvature at every point. The corresponding cubics are determined by their control polygon.

Topics: DTIC Archive, Fiorot, Jean Charles, Schiavon, Laurent, UNIVERSITE DE VALENCIENNES ET DU...

Some contour properties can be derived in parallel by a string or cycle of automata in linear time, faster than can be done with a single processor. In particular the intersection points of two contours, the straightness of a line, the union or intersection of two contours, and polygonal approximations of a contour are computed in linear time. (Author)

Topics: DTIC Archive, Dubitzki,Tsvi, MARYLAND UNIV COLLEGE PARK COMPUTER SCIENCE CENTER, *PARALLEL...

The POS polyline smoothing algorithm was developed to reduce the needed storage and rendering complexity of polylines by the removal of vertices with two goals in mind. First was to define a single algorithm that would produce a good enough result with varying characteristics, which are user defined. The concept of good enough is built on the trade of time vs. precision, where the best result takes the longest time and the quickest maybe less than desirable form. The second goal was to...

Topics: DTIC Archive, Layne, Geary, NAVAL RESEARCH LAB STENNIS SPACE CENTER MS MARINE GEOSCIENCES DIV,...

In this notebook a collection of new results is presented in computational geometry, which all concern problems of planar geometry. The first problem is that of triangulating a simple n-vertex polygon; we show that this can be done in time 0(nlogn), by first decomposing in time 0(nlogn) the given polygon into a collection of special polygons, called monotone, which can be individually triangulated in time proportional to their numbers of edges. The second result concerns that all-nearest...

Topics: DTIC Archive, Preparata,F P, ILLINOIS UNIV AT URBANA-CHAMPAIGN COORDINATED SCIENCE LAB, *COMPUTERS,...

In 1898 J. Kuerschak observed that the area of a regular 12-gon is = 3r square. This is variously generalized in the plane and in space. (Author)

Topics: DTIC Archive, Schoenberg,I J, WISCONSIN UNIV MADISON MATHEMATICS RESEARCH CENTER, *GEOMETRY,...

This paper concerns the use of ray sensors to detect the orientation of polygonal and polyhedral objects moving on a belt or slide. The problem is abstracted to the computational domain and the following results obtained. For polygons of n vertices, n sensors are sufficient and (n/2) necessary. For convex polyhedra of n vertices, (6n) sensors are sufficient and (n/4) necessary. Non-convex polyhedra cannot be effectively handled with such sensors.

Topics: DTIC Archive, Natarajan, B K, CARNEGIE-MELLON UNIV PITTSBURGH PA ROBOTICS INST, *AUTOMATION,...

The rapid development of computed tomography, ultrasound, magnetic resonance imaging and other 3D medical imaging modalities has inspired corresponding development of visualization methods for this data. Described in this paper are some of these methods. Emphasized are volume rendering techniques that generate extremely high-quality images directly from the 3D data. Also described are less computation-intensive methods based on extracted polygonal surface representations. The polygon-based...

Topics: DTIC Archive, Fuchs, Henry, NORTH CAROLINA UNIV AT CHAPEL HILL, *MEDICAL COMPUTER APPLICATIONS,...

Many applications in computer graphics and related fields can benefit from automatic simplification of complex polygonal surface models. Applications are often confronted with either very densely over-sampled surfaces or models too complex for the limited available hardware capacity. An effective algorithm for rapidly producing high-quality approximations of the original model is a valuable tool for managing data complexity. In this dissertation, I present my simplification algorithm, based on...

Topics: DTIC Archive, Garland, Michael, CARNEGIE-MELLON UNIV PITTSBURGH PA SCHOOL OF COMPUTER SCIENCE,...

The combination of high-resolution multi-spectral satellite imagery and advanced COTS object-oriented image processing software provides for an automated terrain feature extraction and classification capability. This information, long with elevation data, infrared imagery, a vehicle mobility model and various meta-data (local weather reports Zobler Soil map, etc...), is fed into automated path planning software to provide a stand-alone ability to generate rapidly updateable dynamic mobility...

Topics: DTIC Archive, LOCKHEED MARTIN MISSILES AND FIRE CONTROL DALLAS TX, *GROUND VEHICLES, *REMOTE...

Topics: DTIC Archive, Bozkurt, Gozde, NORTH CAROLINA STATE UNIV AT RALEIGH DEPT OF ELECTRICAL ENGINEERING,...

We consider the following four problems for a set S of k points on a plane, equipped with the rectilinear metric and containing a set R of n disjoint rectangular obstacles (so that distance is measured by a shortest rectilinear path avoiding obstacles in R): (a) find a closet pair of points in S, (b) find a nearest neighbor for each point in S, (c) compute the rectilinear Voronoi diagram of S, and (d) compute a rectilinear minimal spanning tree of S. We describe O((n + k) log(n + k)) time...

Topics: DTIC Archive, Guha, Sumanta, WISCONSIN UNIV-MILWAUKEE DEPT OF ELECTRICAL ENGINEERING AND COMPUTER...

The author presents this study an investigation into the use of texturizing on the Silicon Graphics, Inc. IRIS for real-time computer animation. Using a tool designed specifically for the IRIS for defining texture patterns, two approaches to the design and implementation of software functions to fill objects with multi-color texture patterns are discussed. The first approach makes use of the IRIS patterning hardware to fill objects with multi-color texture patterns. Realizing the limitations of...

Topics: DTIC Archive, Meier, Timothy W, NAVAL POSTGRADUATE SCHOOL MONTEREY CA, *TEXTURE, *COMPUTER...

Applications which run on parallel supercomputers are often characterized by massive datasets. Converting these vast collections of numbers to visual form has proven to be a powerful aid to comprehension. For a variety of reasons, it may be desirable to provide this visual feedback at runtime. One way to accomplish this is to exploit the available parallelism to perform graphics operations in place. In order to do this, we need appropriate parallel rendering algorithms and library interfaces....

Topics: DTIC Archive, Crockett, Thomas W, INSTITUTE FOR COMPUTER APPLICATIONS IN SCIENCE AND ENGINEERING...

A convex polygon in R2, or a convex polyhedron in R3, will be called a tile. A connected set P of tiles is called a partial tiling if the intersection of any two of the tiles is either empty, or is a vertex or edge (in R3: or face) of both. P is called strongly normal (SN) if, for any partial tiling P' P and any tile P epsilon P', the neighborhood N(P,P) of P (the union of the tiles of P' that intersect P) is simply connected. Let P be SN, and let N*(P,P) be the excluded neighborhood of P in P...

Topics: DTIC Archive, Saha, Punam K., MARYLAND UNIV COLLEGE PARK COMPUTER VISION LAB, *TOPOLOGY, *POLYGONS,...

An algorithm is given that finds the intersection of two convex polygons. It is coded in Fortran for the IBM PC desktop computer. The program is robust and fast. It has been used successfully in targeting applications that require a rapid determination of the common intersection of more than 100 convex polygons, each specified by more than 150 vertices.

Topics: DTIC Archive, DiDonato, Armido R, NAVAL SURFACE WARFARE CENTER DAHLGREN DIV VA, *ALGORITHMS,...

Declarative modeling aims at producing scenes or objects from the user's requirements, and be will briefly introduced. We will then present MDC, a Declarative Modeler for Curves, and the different ways for describing curves. We mainly focus on our internal model which allows us to simply manipulate B-splines curves preserving their properties.

Topics: DTIC Archive, Rossignol, Vincent, Daniel, Marc, INSTITUT DE RECHERCHE EN INFORMATIQUE DE NANTES...

This report describes a method and a system for automatic generation of multi-technology process-outlines. A process outline is a sequence of operations leading from the raw workpiece to the required finished part. The method is applied to axisymmetric parts produced by a set of deep-drawing and machining processes. The method, the plan synthesis tactics and the forms of representations are based on the study and evaluation of the technological knowledge. The input is a CAD representation of...

Topics: DTIC Archive, Eshel, Gad, PURDUE UNIV LAFAYETTE IN SCHOOL OF INDUSTRIAL ENGINEERING, *PRODUCTION...

Different constructions of multisided surface patches (due to Sabin, Hosaka-Kimura, Warren, Loop-DeRose, etc.) are studied via considering base points of their parametrizations. This analysis shows hidden interrelations between various cases and enables to find new efficient control point schemes in more general situations. In particular, toric patches are introduced.

Topics: DTIC Archive, Karciauskas, Kestutis, Krasauskas, Rimvydas, VILNIUS UNIV (LITHUANIA) DEPT OF...

Arrangements of planar objects represent one of the main topics of computational geometry. We propose an approach that allows reliable computations on arrangements of curves. This approach is based on the use of polygonal approximations for the curves composing the arrangement, and the questions to be answered concern the topological and geometric properties of the approximating arrangement of polygonal lines.

Topics: DTIC Archive, Neagu, Manuela, Lacolle, Bernard, JOSEPH FOURIER UNIV LME-IMAG GRENOBLE (FRANCE),...

The kernel K(P) of a simple polygon P with n vertices is the locus of the points internal to P from which all vertices of P are visible. Equivalently, K(P) is the intersection of appropriate half-planes determined by the polygon's edges. Although the intersection of n generic half-planes is known to require time 0(n log n), we show that one can exploit the ordering of the half-planes corresponding to the sequence of the polygon's edges to obtain a kernel finding algorithm which runs in time...

Topics: DTIC Archive, Lee,D T, ILLINOIS UNIV AT URBANA-CHAMPAIGN COORDINATED SCIENCE LAB, *ALGORITHMS,...

Lipton and Tarjan's planar separator theorem (LT77, L177) is notable example of a systematic technique for introducing a computational tool, i.e., divide-and-conquer, into a whole class of relate problems, i.e., planar graph problems. Drawing its inspiration from this philosophy, this paper presents a theoretical result on polygon decomposition which can be applied to derive a number of efficient algorithms for geometric problems, in particular, problems of convex decompositions, triangulation,...

Topics: DTIC Archive, Chazelle, Bernard, CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE,...